#include "thread.h"

extern func_BiTree fBiTree;

/**
 *  功 能：
 *      线索化二叉树 -- 后序线索化
 *  参 数：
 *      root：要线索化的树的根节点
 *      ptmp：用于保留前驱节点
 *  返回值：
 *      无
 **/
void post_thread(BiTNode *root, BiTNode **ptmp)
{
    if ((root == NULL))
        goto END;

    post_thread(root->lchild, ptmp);
    post_thread(root->rchild, ptmp);

    if (root->lchild == NULL)
    {
        root->lchild = *ptmp;
        root->lTag = 1;
    }
    if (*ptmp != NULL && (*ptmp)->rchild == NULL)
    {
        (*ptmp)->rchild = root;
        (*ptmp)->rTag = 1;
    }
    (*ptmp) = root;

END:
    return;
}

/**
 *  功 能：
 *      后序线索化二叉树的前驱节点 
 *  参 数：
 *      root：要查找的节点
 *  返回值：
 *      成功：节点的后继节点
 *      失败：NULL
 **/
BiTNode *post_thread_prevNode(BiTNode *root)
{
    BiTNode *ret = NULL;

    if (root == NULL)
        goto END;

    // 如果 lTag 为 1, 就是本应该的前驱节点
    if (root->lTag == 1)
        ret = root->lchild;
    // 如果 rTag 为 1, 那么 rchild 指针域就是后继节点
    else if (root->rchild && root->rTag != 1)
        ret = root->rchild;
    // 如果 rTag 为 0, 并且同时 rTag 为0， 那么 rchild 指针域就是前驱节点
    // 这是因为在左右子树都存在的情况下，不会去进行线索化，但是其节点总归要前驱
    // 节点和后继节点的其中一个
    else if (root->lTag == 0 && root->rTag == 1)
        ret = root->lchild;
    else
        ret = root->lchild;

END:
    return ret;
}

/**
 *  功 能：
 *      后序线索化二叉树的后继节点 
 *  参 数：
 *      root：要查找的节点
 *  返回值：
 *      成功：节点的后继节点
 *      失败：NULL
 **/
BiTNode *post_thread_nextNode(BiTNode *root)
{
    BiTNode *ret = NULL;

    if (root == NULL)
        goto END;

END:
    return ret;
}

/**
 *  功 能：
 *      遍历线索化二叉树 - 使用后继节点
 *  参 数：
 *      root：要遍历的线索二叉树的根节点
 *  返回值：
 *      无
 **/
void post_thread_Older_byNextNode(BiTNode *root)
{
    if (root == NULL)
        goto END;

END:
    printf("\n");
    return;
}

/**
 *  功 能：
 *      遍历线索化二叉树 - 使用前驱节点
 *  参 数：
 *      root：要遍历的线索二叉树的根节点
 *  返回值：
 *      无
 **/
void post_thread_Older_byPrevNode(BiTNode *root)
{
    int i = 0;
    if (root == NULL)
        goto END;

    while (root)
    {
        printf("%c ", root->data);
        root = post_thread_prevNode(root);
        i++;
    }

END:
    printf("\n");
    return;
}

/**
 *  功 能：
 *      遍历线索化二叉树 - 使用前驱节点
 *  参 数：
 *      root：要遍历的线索二叉树的根节点
 *  返回值：
 *      无
 **/
void post_thread_Older_normal(BiTNode *root)
{
    if (root == NULL)
        goto END;
    /**
     *  定义一个缓存区，用于保存反向后序遍历的顺序
     *  其中这个地方比较推荐使用的栈，省去多余空间的浪费
     */
    int i = 0, j = 0;
    unsigned char buf[128] = {0};

    while (root)
    {
        buf[i] = root->data;
        root = post_thread_prevNode(root);
        i++;
    }

    for (j = i; j > 0; j--)
        printf("%c ", buf[j - 1]);
END:
    return;
}

funThread fthread = {
    post_thread,

    post_thread_Older_byNextNode,
    post_thread_Older_byPrevNode,
    post_thread_Older_normal,

    post_thread_nextNode,
    post_thread_prevNode

};

#if 0

在后序线索二叉树中查找结点*p的后继
1、若结点*p为根，则无后继；
2、若结点*p为其双亲的右孩子，则其后继为其双亲；
3、若结点*p为其双亲的左孩子，且双亲无右子女，则其后继为其双亲；
4、若结点*p为其双亲的左孩子，且双亲有右子女，则结点*p的后继是其双亲的右子树中按后序遍历的第一个结点。

#endif
